#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>

typedef struct IN_DATA Indata;
typedef struct TREENODE TreeNode;
typedef char Element;
typedef struct STACK Stack;
typedef TreeNode* Item;
struct IN_DATA{
	Element elm;
	int  left_i;
	int  right_i;
};

struct TREENODE{
	Element elm;
	TreeNode *left;
	TreeNode *right;
	TreeNode *father;
	_Bool visited_left;
	_Bool visited_right;
};

struct STACK{
	Item item;
	Stack* next;
};



Stack* initStack();
void destroyStack(Stack*);
_Bool stackEmpty(Stack*);
void push(Stack*,Item);
Item pop(Stack*);
void preorder(TreeNode *root);
void preOrder2(TreeNode*);
void inorder(TreeNode *root);
void inOrder2(TreeNode *root);
void inorder2(TreeNode *root);
void inorder3(TreeNode *root);
void postorder(TreeNode *root);
void postOrder2(TreeNode*);
void postOrder3(TreeNode*);

int main(void){
	int nodes;
	char tmp;
	scanf("%d",&nodes);
	while( (tmp=getc(stdin)) != '\n' );
	Indata data[100];
	char l,r;
	TreeNode *nodePtr[nodes];
	for(int i=0;i<nodes;i++){
		scanf("%c %c %c",&(data[i].elm),&l,&r);
		if( l != '-' )
			data[i].left_i = l - '0';
		else 
			data[i].left_i=-1;
		if( r != '-' )
			data[i].right_i = r - '0';
		else
			data[i].right_i=-1;
		while( (tmp=getc(stdin)) != '\n' );
		nodePtr[i]=malloc(sizeof(TreeNode));
		nodePtr[i]->elm=data[i].elm;
		nodePtr[i]->left=nodePtr[i]->right=nodePtr[i]->father=NULL;
		nodePtr[i]->visited_left=false;
		nodePtr[i]->visited_right=false;
	}
	for(int i=0;i<nodes;i++){
		printf("%c %d %d\n",(data[i].elm),(data[i].left_i),(data[i].right_i));
	}

	for(int i=0;i<nodes;i++){
		if( data[i].left_i != -1 ){
			nodePtr[i]->left=nodePtr[ data[i].left_i ]; 
			nodePtr[ data[i].left_i ]->father=nodePtr[i];
		}
		if( data[i].right_i != -1 ){
			nodePtr[i]->right=nodePtr[ data[i].right_i ]; 
			nodePtr[ data[i].right_i ]->father=nodePtr[i];
		}
	}
	TreeNode *root=nodePtr[0];
	while( root->father )
		root=root->father;
	//preorder(root);
	//preOrder2(root);
	//inorder(root);
printf("\n");
printf("\n");
postOrder3(root);
	//postOrder2(root);
	//inorder3(root);
	//postorder(root);
	return 0;
}


void preorder(TreeNode *root){
	if ( NULL == root )
		return;
	printf("%c", root->elm);
	preorder( root->left);
	preorder( root->right);
	return;
}
void inorder(TreeNode *root){
	if ( NULL == root )
		return;
	inorder( root->left );
	printf("%c",root->elm);
	inorder( root->right );
	return;
}
void postorder(TreeNode *root){
	if ( NULL == root )
		return;
	postorder(root->left);
	postorder(root->right);
	printf("%c",root->elm);
	return;
}

Stack *initStack(){
	Stack *new=malloc(sizeof(Stack));
	new->next=NULL;
	return new;
}

void destroyStack(Stack *s){
	Stack *next;
	while( s ){
		next=s->next;
		free(s);
		s=next;
	}
	return;
}
_Bool stackEmpty(Stack *s){
	if( s->next )
		return false;
	return true;
}
void push(Stack *s,Item item){
	Stack *new=malloc(sizeof(Stack));
	new->item=item;
	new->next=s->next;
	s->next=new;
	return;
}
Item pop(Stack *s){
	Item item=s->next->item;
	Stack *tmp=s->next->next;
	free(s->next);
	s->next=tmp;
	return item;
}
void inorder2(TreeNode *root){
	if( !root )return;
	TreeNode *current=root;
	Stack *s=initStack();
	push(s,current);
	do{
		if( current->left ){	// there is a left child
			current=current->left;
			push(s,current);
		}else{		// left child is NULL
			current=pop(s);
			printf("%c",current->elm);
			if( current->right ){	// there is a right child
				current=current->right;
				push(s,current);
			}else{					// right child is NULL
				current=pop(s);	
				printf("%c",current->elm);
				current=current->right;
			}
		}
	}while( !stackEmpty(s) || !current );
}

void inorder3(TreeNode *root){
	Stack *s=initStack();
	while( !stackEmpty(s) || root ){
sleep(2);
printf("haha\n");
		push(s,root);
		while( root->left ){
			root=root->left;
			push(s,root);
		}
		root=pop(s);
		printf("%c",root->elm);
		if( root->right ){
			root=root->right;
		}else{
			//root=pop(s);
			//printf("%c",root->elm);
			//root=root->right;
			root=root->right;
			while( !stackEmpty(s) && !root ){
				root=pop(s);
				printf("%c",root->elm);
				root=root->right;
			}
		}
	}
}


void preOrder2(TreeNode *root){
	Stack *s=initStack();
	while( root || !stackEmpty(s) ){
		while( root ){
			printf("%c",root->elm);
			push(s,root);
			root=root->left;
		}
		if ( !stackEmpty(s) ){
			root=pop(s)->right;
		}
	}
}


void inOrder2(TreeNode *root){
	Stack *s=initStack();
	TreeNode *tn;
	while( root || !stackEmpty(s) ){
		while( root ){
			push(s,root);
			root=root->left;
		}
		if ( !stackEmpty(s) ){
			tn=pop(s);
			printf("%c",tn->elm);
			root=tn->right;
		}
	}
}

void postOrder2(TreeNode *root){
	Stack *s=initStack();
	TreeNode *head=root;
	while( (false==head->visited_left) || (false==head->visited_right) || !stackEmpty(s) ){
		while( root && !(root->visited_left) ){
			root->visited_left=true;
			push(s,root);
			root=root->left;
		}
		if ( !stackEmpty(s) ){
			root=pop(s);
			if( root->visited_right ){
				printf("%c\n",root->elm);
			}else{
				root->visited_right=true;
				push(s,root);
				root=root->right;
			}
		}
	}
	return;
}
void postOrder3(TreeNode *root){
	Stack *s=initStack();
	//while( (false==head->visited_left) || (false==head->visited_right) || !stackEmpty(s) ){
	while( 1 ){
		//while( !root->visited_left ){
		//	root->visited_left=true;
		//	if( !(root->left) ) break;
		//	root=root->left;
		//	push(s,root);
		//}
		while( root && !root->visited_left ){
printf("PUSH %c\n",root->elm);
			push(s,root);
			if( root->left )
			root=root->left;
		}
		if( !stackEmpty(s) )root=pop(s);
		if ( !root->visited_right ){
			root->visited_right=true;
			if( root->right ){
				root=root->right;
			}
		}else{		// visited_left == true && visited_right==true
			if( stackEmpty(s) ){break;}
			else{
				root=pop(s);
				printf("%c",root->elm);
			}
		}
	}
	return;
}
